#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <math.h>
#include<algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    int x[5] = { 1,-1,0,0 };
    int y[5] = { 0,0,1,-1 };
    int arr[110][110] = { 0 };
    bool dp(int di, int dj, string& word, int index, vector<string>& board)
    {
        bool flag = false;
        int l1 = board.size();
        int l2 = board[0].size();
        if (index >= word.size()) return true;
        arr[di][dj] = 1;
        for (int i = 0; i < 4; i++)
        {
            int xi = di + x[i];
            int yi = dj + y[i];
            if (xi >= 0 && xi < l1 && yi >= 0 && yi < l2 && board[xi][yi] == word[index]&&arr[xi][yi]==0)
            {
                flag = dp(xi, yi, word, index + 1, board);
                if (flag) break;
            }
        }
        arr[di][dj] = 0;
        return flag;
    }
    bool exist(vector<string>& board, string word) {
        int len = board.size();
        int l = board[0].size();
        if (len <= 0) return false;
        if (l * len < word.size()) return false;
        for (int i = 0; i < len; i++)
        {
            for (int j = 0; j < l; j++)
            {
                if (board[i][j] == word[0])
                {
                    if (dp(i, j, word, 1, board)) return true;
                }
            }
        }
        return false;
    }
};

int main() {
    vector<string> borad = {"XYZE","SFZS","XDEE"};
    string word = "XYZZED";
    bool ret = Solution().exist(borad,word);
    if (ret) cout << "true";
    return 0;
}
